package other

//509. 斐波那契数-迭代法
//时间复杂度O(N)，空间复杂度O(1)
//https://leetcode-cn.com/problems/fibonacci-number/
func Fib(N int) int {
	if N <= 1 {
		return N
	}

	//特殊值
	pre, prePre := 1, 0
	//初始化
	cur := 0
	//迭代
	for i := 2; i <= N; i++ {
		cur = pre + prePre

		prePre = pre
		pre = cur
	}

	return cur
}

//509. 斐波那契数-缓存
//时间复杂度O(N), 空间复杂度O(N)
func Fib2(N int) int {
	if N <= 1 {
		return N
	}

	cache := make(map[int]int)
	cache[0], cache[1] = 0, 1

	for i := 2; i <= N; i++ {
		cache[i] = cache[i-1] + cache[i-2]
	}

	return cache[N]
}

//509. 斐波那契数-递归
//时间复杂度:O(2^N),空间复杂度O(N)
func Fib3(N int) int {
	if N <= 1 {
		return N
	}

	return Fib2(N-1) + Fib2(N-2)
}
